/**
 * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

 

示例 1:



输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]
Example 2:


输入：root = [4,2,7,1,3], val = 5
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-in-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST1 = function (root, val) {

    if (!root) return null
    //深度优先遍历
    let res = null
    const dfe = (root) => {
        if (!root) return
        if (root.val === val) {
            res = root
        }

        dfe(root.left)
        dfe(root.right)
    }
    dfe(root)

    return res
};


var searchBST = function (root, val) {

    //利用二分搜索树的特性 使用二分法
    if (!root) return null

    if (root.val === val) {
        return root
    }

    return searchBST(val > root.val ? root.right : root.left, val)
};
